/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var findTargetSumWays = function (nums, target) {
  //计算数组元素之和
  const sum = nums.reduce((acc, num) => acc + num, 0)

  //如果sum+target小于0或者sum+target为奇数，表示无法分割
  if (sum + target < 0 || (sum + target) % 2 == 1) return 0

  //转换成0-1背包问题：在数组nums中挑选出若干个，使其和为subSet
  let subSet = (sum + target) / 2

  //创建动态数组dp：dp[i][j]表示前i个元素组成j的方案数量
  let dp = new Array(subSet + 1).fill(0)//压缩成一维滚动数组，减少空间复杂度
  //初始状态
  dp[0] = 1 //前0个元素和为0的方案数量为1，即一个元素都不选

  for (let num of nums) {
    //逆序避免重复选择元素；j>=num保证状态转移的有效性，避免访问负数下标
    for (let j = subSet; j >= num; j--) {
      dp[j] = dp[j] + dp[j - num]
    }
  }

  //返回数组所有元素中，组成subSet的方案个数
  return dp[subSet]

};

console.log(findTargetSumWays([1, 2, 3], 3))